package Trie

// 字典树：
/*
	1. 单词结尾表示：需要使用一个 bool 类型，辨识当前节点是否是结尾字符
		叶子结点是 单词结尾
		非叶子节点 也可能是单词的结尾
	2. 实现功能
		增加单词
		搜索单词
*/


// 定义树的节点
type Node struct {
	// 1. 保存当前字符
	//C byte
	// 使用hash存储，就不需要当前的字符了，它已经在key中了
	// 2. 若干个子节点: 字符： 节点
	Children map[byte]*Node
	// 3. 标识节点是否是一个单词最后的一个字符
	isWord bool
}

// 给子节点 列表添加新的节点
func (n *Node) Add(c byte) {
	// 构造节点：  nil 类型 map 不可直接使用添加元素等
	node := Node{
		Children: make(map[byte]*Node, 0),
	}
	// 添加
	n.Children[c] = &node
}

// 返回子节点 列表 长度
//func (n *Node) Len() int {
//	return len(n.Children)
//}

// 设置节点的 isword
func (n *Node) SetIsword(flag bool) {
	n.isWord = flag
}

// 整棵树的根节点
type Trie struct {
	// 字典树的根节点
	Root *Node
}


// 随便初始化根节点为 "/" 吧
func (t *Trie) Init() *Trie {
	t.Root = &Node{
		make(map[byte]*Node, 0),
		false,
	}
	return t
}


// 外部调用初始化一个 字典树
func New() *Trie { return new(Trie).Init() }


// 添加单词
// 时间复杂度：
func (t *Trie) Add(word string) {
	// 转换为 字符
	w := []byte(word)
	// 找到每一个节点
	cur := t.Root
	// 遍历 word的每一个字符
	for _, c := range w {
		// 1. 查找子节点中是否包含当前字符
		// 如果不包含, 添加一下
		if _, ok := cur.Children[c]; !ok {
			// 添加新节点
			cur.Add(c)
		}
		// cur 指向下一个子节点
		cur = cur.Children[c]
	}
	// 将最后一个节点字符的 尾设置为 true
	cur.SetIsword(true)
}


//// 查找子节点中是否包含指定字符： 私有方法
//func (t *Trie) containsChar(c byte, childrens []*Node) int {
//	// 线性遍历查找
//	for i, node := range childrens {
//		// 查找到既返回索引
//		if node.C ==  c {
//			return i
//		}
//	}
//	return -1
//}


// 判断是否包含指定的单词
// 不仅能找到单词，并且单词的结尾必须是 isWord = true 才说明有这个单词
func (t *Trie) Contains(word string) bool {
	// 转换为 字符
	w := []byte(word)
	// 找到每一个节点
	cur := t.Root
	// 遍历 word的每一个字符
	for _, c := range w {
		// 1. 查找子节点中是否包含当前字符
		if _, ok :=  cur.Children[c]; !ok {
			return false
		}
		// cur 指向下一个子节点
		cur = cur.Children[c]
	}
	// 判断最后一个单词是否是 单词末尾 cur.isWord == true,
	// 直接缩写为 cur.isWord
	return cur.isWord
}

